(define gensym
  (letrec
      ((curnum 0))
    (lambda()
      (set! curnum (+ curnum 1))
      curnum
      )))


(define cse
  (lambda (orgExp)
    (letrec
        (
         (database '())
         (letclauses '())
         (application?
          (lambda (exp)(and (pair? exp) (not (eq? 'quote (car exp))))))

         (addToLetClauses 
          (lambda (symbl lst exp)
            (cond
              ((null? lst)
               (set! letclauses (append letclauses (list (list symbl exp)))))
              ((equal? symbl (caar lst))
               (if exp (set-car! (cdar lst) exp)))
              (else (addToLetClauses symbl (cdr lst) exp)))))
                      
         (registerAtDatabase
          (lambda (exp lst symbl ret)
            (cond
              ((null? lst)
                 (set! database (cons (list symbl exp #f) database))
                 (ret))
              ((equal? exp (cadar lst))
               (set-car! (car lst) symbl)
               (ret))
              (else (registerAtDatabase exp (cdr lst) symbl ret)))))
        
         (checkSimilar
          (lambda (exp lst retYes retNo)
            (cond
              ((null? lst)
               (let ((newEntry (list #f exp #f)))
                 (set! database (cons newEntry database))
                 (retNo newEntry)))
              ((equal? exp (cadar lst))
               (if (caar lst) 
                   (retYes (car lst))
                   (let
                       ((newSymbol (gensym)))
                     (set-car! (car lst) newSymbol)
                     (registerAtDatabase
                      ((caddar lst) #f)
                      database
                      newSymbol
                      (lambda () (retYes (car lst)))))))
              (else (checkSimilar exp (cdr lst) retYes retNo)))))
         
         (scanExp 
          (lambda (exp ret)
            (if
             (null? exp) 
             (ret (lambda(s) exp))
             (scanExp
              (cdr exp)
              (lambda (ret-cdr)
                (cond
                  ((application? (car exp))
                   (checkSimilar 
                    (car exp)
                    database
                    (lambda (entry) 
                      (ret (lambda (s) 
                             (if s (addToLetClauses (car entry) letclauses ((caddr entry)s)))
                             (cons (car entry) (ret-cdr s)))))
                    (lambda (newEntry)   
                      (scanExp
                       (car exp)
                       (lambda (ret-car)
                         (set-car! (cddr newEntry) ret-car)
                         (ret (lambda (s) (if (car newEntry)
                                            (begin
                                              (if s (addToLetClauses (car newEntry) letclauses ((caddr newEntry)s)))
                                              (cons (car newEntry) (ret-cdr s)))
                                            (cons (ret-car s) (ret-cdr s))))))))))
                  (else (ret (lambda (s) (cons (car exp) (ret-cdr s))))))))))))
      ; MAIN:
      (if (application? orgExp)
          (scanExp 
           orgExp 
           (lambda(ret) 
             (map
              (lambda (clause)
                (if (and (car clause) (caddr clause))
                    (addToLetClauses (car clause) letclauses ((caddr clause) #t))))
              database)               
             (if (null? letclauses) 
                 (ret #f)
                 (list 'let* letclauses (ret #f)))))
          orgExp))))

(define test19 '(((((d b a d) (d b a d)) b (d b a d) b) b c d) ((((d b a d) (d (c c (d b a d) c) (d b a d) (c c (d b a d) c))) (((((d b a d) (d b a d)) b (d b a d) b) b c d) (((d b a d) (d b a d)) (d (c c (d b a d) c) (d b a d) (c c (d b a d) c)) (((d b a d) (d b a d)) b (d b a d) b) (a c d c (c c (d b a d) c)) (((d b a d) (d b a d)) b (d b a d) b)) ((((d b a d) (d b a d)) b (d b a d) b) b c d) ((d b a d) (d b a d)) (((d b a d) (d b a d)) b (d b a d) b)) (c c (d b a d) c) (((d b a d) (d b a d)) b b) (((((d b a d) (d b a d)) b (d b a d) b) b c d) (((((d b a d) (d b a d)) b (d b a d) b) b c d) (((d b a d) (d b a d)) (d (c c (d b a d) c) (d b a d) (c c (d b a d) c)) (((d b a d) (d b a d)) b (d b a d) b) (a c d c (c c (d b a d) c)) (((d b a d) (d b a d)) b (d b a d) b)) ((((d b a d) (d b a d)) b (d b a d) b) b c d) ((d b a d) (d b a d)) (((d b a d) (d b a d)) b (d b a d) b)) (a b) ((d b a d) (d (c c (d b a d) c) (d b a d) (c c (d b a d) c))))) (((d b a d) (d (c c (d b a d) c) (d b a d) (c c (d b a d) c))) (((((d b a d) (d b a d)) b (d b a d) b) b c d) (((d b a d) (d b a d)) (d (c c (d b a d) c) (d b a d) (c c (d b a d) c)) (((d b a d) (d b a d)) b (d b a d) b) (a c d c (c c (d b a d) c)) (((d b a d) (d b a d)) b (d b a d) b)) ((((d b a d) (d b a d)) b (d b a d) b) b c d) ((d b a d) (d b a d)) (((d b a d) (d b a d)) b (d b a d) b)) c) ((d b a d) (d (c c (d b a d) c) (d b a d) (c c (d b a d) c)))) (((d b a d) (d b a d)) b (d b a d) b) (((((d b a d) (d b a d)) b (d b a d) b) b c d) (((((d b a d) (d b a d)) b (d b a d) b) b c d) (((d b a d) (d b a d)) (d (c c (d b a d) c) (d b a d) (c c (d b a d) c)) (((d b a d) (d b a d)) b (d b a d) b) (a c d c (c c (d b a d) c)) (((d b a d) (d b a d)) b (d b a d) b)) ((((d b a d) (d b a d)) b (d b a d) b) b c d) ((d b a d) (d b a d)) (((d b a d) (d b a d)) b (d b a d) b)) (a b) ((d b a d) (d (c c (d b a d) c) (d b a d) (c c (d b a d) c)))) (((d b a d) (d b a d)) b b)))

; the answer is 10
(define answer (cse test19))
(+ (car (cadr (cadr answer))) (length (cadr answer)))


